package 力扣.动态规划;
//给你一个整数 n，请返回长度为 n 、仅由元音
// (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
//字符串 s 按 字典序排列 需要满足：对于所有有效的 i，
// s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。
public class 统计字典序元音字符串的数目 {
    public static void main(String[] args) {

    }
    public static int countVowelStrings(int n) {
        //n为长度，后边代表的以哪个元音字符结尾
        int[][] dp = new int[n + 1][5];
        for (int i = 0; i < 5; i++) {
            dp[1][i]=1;
        }
        for (int i = 2; i <n+1 ; i++) {
            //以u结尾，可以在任意字符串后边加u
            dp[i][4]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3]+dp[i-1][4];
            //以o结尾
            dp[i][3]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3];
            //以i结尾
            dp[i][2]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
            //以e结尾
            dp[i][1]=dp[i-1][0]+dp[i-1][1];
            //以a结尾
            dp[i][0]=dp[i-1][0];
        }
        return dp[n][0]+dp[n][1]+dp[n][2]+dp[n][3]+dp[n][3]+dp[n][4];
    }
}
